package com.beimihu.leetcode.数据结构;

public class DoublyLinkedListSentinel {
    static class Node{
        Node prev;
        Node next;
        int value;

        public Node(Node prev,Node next,int value){
            this.prev = prev;
            this.next = next;
            this.value = value;
        }



    }
    private Node head;//头部
    private Node tail;//尾部
    public DoublyLinkedListSentinel(){
        head = new Node(null,null,66);
        tail = new Node(null,null,77);
        head.next=tail;
        tail.prev=head;
    }

    private Node findNode(int index){
        int i = -1;
        for(Node p = head;p != tail;p = p.next,i++){
            if(i == index){
                return p ;
            }
        }
        return null;
    }

    private void insert(int index,int value){
        Node prev = findNode(index - 1);
        if (prev == null){
            throw new IllegalArgumentException("越界");
        }

        Node next = prev.next;
        Node inserted = new Node(prev,next,value);

        prev.next = inserted;
        next.prev = inserted;

    }

    public void remove(int index){
        Node prev = findNode(index-1);

        if (prev == null){
            throw new IllegalArgumentException("越界");
        }

        Node removed = prev.next;
        if(removed == null){
            throw new IllegalArgumentException("越界");
        }
        Node next = removed.next;

        prev.next = next;
        next.prev = prev;
    }

    public void addLast(int value){
        Node last = tail.prev;

        Node inserted = new Node(last,tail,value);
        last.next = inserted;
        tail.prev = inserted;

    }

    public void removeLast(){
        Node remove = tail.prev;
        if(remove == null){
            throw new IllegalArgumentException("越界");
        }
        Node prev =  remove.prev;
        prev.next = tail;
        tail.prev = prev;
    }

    public void addFirst(int value){

    }

}
